package algorithms.sorts;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 6, 1000, 45, 78, -25, 3, 13, 1, 10, -100};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {//轮流插入排序：i=n*gap+m为第m组索引为n的元素插入排序
                insert(arr, i, gap);
            }
        }
    }

    private static void insert(int[] arr, int index, int step) {
        int temp = arr[index];
        int i = index - step;
        while (i >= 0 && temp < arr[i]) {
            arr[i + step] = arr[i];
            i -= step;
        }
        arr[i + step] = temp;
    }
}
